Méthodes de Monte Carlo

3. Estimation : Estimation de la fonction des valeurs des actions

3.1. Méthode par exploration des départs

Lorsqu'un modèle n'est pas disponible, il est utile d'estimer la fonction des valeurs des actions en vue de construire une stratégie optimale. En effet, avec un modèle connu, les valeurs des états sont suffisantes pour déterminer une stratégie optimale : il suffit de regarder les états suivants donnés par les actions prises sur les états et de sélectionner les meilleures actions. Mais sans modèle, les valeurs des états ne sont pas suffisantes et il faut donc estimer la valeurs de chaque action prise sur un état donné pour définir une stratégie optimale par la suite.

L'objectif est donc d'estimer $q_\pi(s,a)$, c'est-à-dire le gain moyen retourné à l'agent lorsqu'il est dans un état $s$ et qu'il prend l'action $a$ en suivant la stratégie $\pi$. Les méthodes de Monte Carlo utilisées pour cela sont sensiblement les mêmes que celles utilisées pour prédire les valeurs des états, sauf qu'ici il faut estimer les paires état-action. Il faut donc visiter les paires état-action plutôt que les états. On retrouve donc les deux méthodes FVMC et EVMC.

Le problème est qu'un grand nombre de paires d'état-action peuvent ne jamais être visitées. En effet, si la stratégie $\pi$ est déterministe, alors l'agent n'observera des retours que sur une action particulière pour un état donné... et sans retour à moyenner, aucune amélioration de l'estimation ne pourra se faire. Il faut donc obligatoirement visiter toutes paires d'état-action, c'est-à-dire visiter toutes les actions de chaque état de l'environnement.

C'est un problème général de maintien de l'exploration dont nous avons déjà parlé lorsque nous avons étudié le problème du bandit manchot. Une manière de maintenir l'exploration est que chaque nouvel épisode démarre sur une paire état-action aléatoire, de sorte que toutes les paires aient une probabilité non nulle d'être sélectionnée. Cela va garantir que sur un nombre infini d'épisodes, toutes las actions seront visitées pour chacun des états de l'environnement. Cette méthode repose sur l'hypothèse d'exploration des départs (exploring starts).

Cette hypothèse peut toutefois poser problème dans certains problèmes qui ne peuvent pas être analysés de cette manière. Un méthode alternative pour s'assurer que toutes les paires état-action sont rencontrées est de ne considérer que les stratégies stochastiques dont les probabilités de visiter une action sur chaque état sont non nulles. Nous verrons deux variantes de cette approche plus tard.

Algorithme